package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName RadixSort
 * @Description 基数排序
 * @Detail detail
 * @Author MyPC
 * @Date 2020/8/7
 * @Version 1.0
 */
public class RadixSort {

    public static void main(String[] args) {
        int arr[]={78,15,2,4,4,68,8,1,16,18,82,66,66,76,86,96,66,66,76,76,54,1};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    /**
     * 排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr){
        // 合法性校验
        if(arr.length==0){
            return null;
        }
        // 每个存放元素的桶的容量,可自定义
        int bucketLength=10;
        // 桶数组
        int[][] bucketArr=new int[10][bucketLength];
        // 获取最大的数的位数
        int bit = getBit(getMax(arr));
        // 外层循环次数与位数保持一致
        for(int i=1;i<=bit;i++){
            // 用于存储对应桶的元素的个数
            int[] flag=new int[10];
            // 1、遍历元素，将元素存入桶数组中
            for (int j=0;j<arr.length;j++){
                // 存放的桶的索引与对应的位上的数保持一致
                int index = getBitNum(arr[j], i, bit);
                // 对应的桶
                int[] bucket = bucketArr[index];
                // 桶容量校验
                if(flag[index]==bucketLength){
                    throw new ArrayIndexOutOfBoundsException("桶容量不足，请扩充桶容量");
                }
                bucket[flag[index]++]=arr[j];
            }
            //2、遍历桶数组，将元素返回给数组
            int index=0;
            for(int j=0;j<bucketArr.length;j++){
                if(flag[j]==0){
                    // 该桶数组没有元素
                    continue;
                }
                // 依次从桶获取元素存储到新数组
                for(int k=0;k<flag[j];k++){
                    arr[index++]=bucketArr[j][k];
                }
            }
        }
        return arr;
    }

    /**
     * 遍历输出桶数组
     * @param bucketArr
     */
    private static void list(int[][] bucketArr){
        for (int i=0;i<bucketArr.length;i++){
            System.out.println(Arrays.toString(bucketArr[i]));
        }
    }

    /**
     * 获取指定位的数字
     * @param source  原数字
     * @param targetBit  指定的位
     * @param bit  数组元素中最大的数字的位数
     * @return
     */
    private static int getBitNum(int source,int targetBit,int bit){
        for (int i=bit;i>targetBit;i--){
            //指定位之前都是取模操作
            source%=(int) Math.pow(10,i-1);
        }
        //指定位求余操作
        return source/(int)Math.pow(10,targetBit-1);
    }

    /**
     * 获取数字有多少位
     * @param num
     * @return
     */
    private static int getBit(int num){
        String str=num+"";
        return str.length();
    }

    /**
     * 获取数组中最大数
     * @param arr
     * @return
     */
    private static int getMax(int[] arr){
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        return max;
    }

}
